package LC;

/**
 * @ClassName LC4
 * @Description: TODO
 * @Author hl
 * @Date 2021/3/21
 * @Version V1.0
 **/
public class LC4 {
    public static void main(String[] args) {
     int []nums1={1,2,4};
     int []nums2={3,5};
        System.out.println(findMedianSortedArrays(nums1,nums2));
    }
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len=nums1.length+nums2.length;
        if(len%2==1){
            double mid=getMid(len/2+1,nums1,nums2);
            return mid;
        }else{
            double mid1=getMid(len/2,nums1,nums2);
            double mid2=getMid(len/2+1,nums1,nums2);
            return  (mid1+mid2)/2;
        }

    }

    private static double getMid(int k,int[] nums1,int[] nums2) {
        int index1=0,index2=0;


     while(true){
         //边界情况
         if(index1==nums1.length){
             return nums2[k+index2-1];
         }
         if(index2==nums2.length){
             return nums1[index1-1+k];
         }
         if(k==1){
             return Math.min(nums1[index1],nums2[index2]);
         }
         //正常情况
         int mid=k/2;
         int newIndex1=Math.min(index1+mid,nums1.length)-1;
         int newIndex2=Math.min(index2+mid,nums2.length)-1;
         if(nums1[newIndex1]<=nums2[newIndex2]){
             k=k-(newIndex1-index1+1);
             index1=newIndex1+1;
         }else{

             k=k-(newIndex2-index2+1);
             index2=newIndex2+1;
         }
     }

    }
}
